#include <bits/stdc++.h>
using namespace std;

const int N = 1005, M = N * N;

namespace mcf
{
struct E
{
    int to, cp, cost, rev;
    E(int to = 0, int cp = 0, int cost = 0, int rev = 0) : to(to), cp(cp), cost(cost), rev(rev) {}
};

struct Mcmf
{
    int v, h[N], dis[N], prev[N], pree[N];
    vector<E> G[N];

    void init(int n)
    {
        v = n;
        for (int i=0; i<=v; ++i)
            G[i].clear();
    }

    void init(int n, int m, int fr[], int to[], int cp[], int w[])
    {
        init(n);
        for (int i=0; i<m; ++i)
            addEdge(fr[i], to[i], cp[i], w[i]);
    }

    void addEdge(int from, int to, int cp, int cost)
    {
        fprintf(stderr, "fr=%d, to=%d, cp=%d, cost=%d\n", from, to, cp, cost);
        G[from].emplace_back(to, cp, cost, G[to].size());
        G[to].emplace_back(from, 0, -cost, G[from].size() - 1);
    }

    int go(int s, int t, int f, int &flow)
    {
        int res = 0;
        memset(h, 0, sizeof(h[0]) * (v + 1));
        while (f)
        {
            priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
            memset(dis, 0x3f3f3f3f, sizeof(dis[0]) * (v + 1));
            dis[s] = 0;
            q.emplace(0, s);
            while (!q.empty())
            {
                auto now = q.top();
                q.pop();
                int v = now.second;
                if (dis[v] < now.first)
                    continue;
                for (int i = 0; i < (int)G[v].size(); ++i)
                {
                    E &e = G[v][i];
                    if (e.cp > 0 && dis[e.to] > dis[v] + e.cost + h[v] - h[e.to])
                    {
                        dis[e.to] = dis[v] + e.cost + h[v] - h[e.to];
                        prev[e.to] = v;
                        pree[e.to] = i;
                        q.emplace(dis[e.to], e.to);
                    }
                }
            }
            if (dis[t] == 0x3f3f3f3f)
                break;
            for (int i = 0; i <= v; ++i)
                h[i] += dis[i];
            int d = f;
            for (int v = t; v != s; v = prev[v])
                d = min(d, G[prev[v]][pree[v]].cp);
            f -= d;
            flow += d;
            res += d * h[t];

            for (int v = t; v != s; v = prev[v])
            {
                E &e = G[prev[v]][pree[v]];
                e.cp -= d;
                G[v][e.rev].cp += d;
            }
        }
        return res;
    }
};
} // namespace mcf

class extmcf1
{
public:
    mcf::Mcmf mcf;
    int d[N];
    int sum, S, T, s, t;
    int baseCost;
    void init(int n, int m, int s, int t, int u[], int v[], int c[], int w1[], int w2[])
    {
        memset(d, 0, sizeof(int) * (n + 1));
        sum = baseCost = 0; S = ++n; T = ++n;
        this->s = s; this->t = t;
        mcf.init(n);


        for (int i=0; i<m; ++i)
        {
            d[v[i]] += w1[i];
            d[u[i]] -= w1[i];
            sum += w1[i];
            baseCost += w1[i] * c[i];
            mcf.addEdge(u[i], v[i], w2[i] - w1[i], c[i]);
        }

        for (int i=1; i<=n; ++i)
        {
            if (d[i] > 0)
            {
                mcf.addEdge(S, i, d[i], 0);
            }
            else if (d[i] < 0)
            {
                mcf.addEdge(i, T, -d[i], 0);
            }
        }

        mcf.addEdge(t, s, 0x3f3f3f3f, 0);
    }  

    int go(int &flow)
    {
        flow = 0;
        int cost = baseCost;
        fprintf(stderr, "baseCost=%d\n", baseCost);
        cost += mcf.go(S, T, 0x3f3f3f3f, flow);
        flow += d[t];
        return cost;
    }
} mcmf;

int n, m;

int u[M], v[M], w1[M], w2[M], cost[M];

void add(int a, int b, int c, int d, int e, int &ecnt)
{
    u[ecnt] = a;
    v[ecnt] = b;
    w1[ecnt] = c;
    w2[ecnt] = d;
    cost[ecnt++] = e;
}

int main(int argc, char const *argv[])
{   
    scanf("%d%d", &n, &m);
    for (int i=0; i<m; ++i)
    {
        scanf("%d%d%d%d%d", u+i, v+i, w1+i, w2+i, cost+i);
    }
    int f = 0;
    mcmf.init(n, m, 1, n, u, v, cost, w1, w2);
    printf("%d\n", mcmf.go(f));
    
    return 0;
}
